package com.kucowka.otc.util.heap;

import java.util.ArrayList;

import com.kucowka.otc.util.heap.exceptions.EmptyHeapExcetion;

public class SimpleMaxHeap<T extends Comparable<T>> implements MaxHeap<T> {

	private ArrayList<T> array = new ArrayList<T>();

	private boolean insert(T t) {
		boolean result = array.add(t);

		if (result) {
			int i = array.size() - 1, j;
			while (i > 0) {
				j = (i - 1) / 2;
				if (array.get(i).compareTo(array.get(j)) > 0) {
					swap(i, j);
					i = j;
				} else {
					break;
				}
			}
		}

		return result;
	}

	private T remove() {
		int i = 0, j;
		T t = array.get(0);
		T lastElement = array.remove(array.size() - 1);

		if (size() > 0) {
			array.set(0, lastElement);

			while (i < array.size()) {
				j = i;
				if (array.size() > 2 * i + 1
						&& array.get(i).compareTo(array.get(2 * i + 1)) < 0) {
					j = 2 * i + 1;
				}

				if (array.size() > 2 * i + 2
						&& array.get(j).compareTo(array.get(2 * i + 2)) < 0) {
					j = 2 * i + 2;
				}

				if (i != j) {
					swap(i, j);
					i = j;
				} else {
					break;
				}
			}
		}

		return t;
	}

	private void swap(int i, int j) {
		T tmp = array.get(i);
		array.set(i, array.get(j));
		array.set(j, tmp);
	}

	public boolean add(T t) {
		return insert(t);
	}

	public int size() {
		return array.size();
	}

	public T peek() {
		if (size() == 0) {
			throw new EmptyHeapExcetion();
		}
		return array.get(0);
	}

	public T pop() {
		if (size() == 0) {
			throw new EmptyHeapExcetion();
		}
		return remove();
	}

	public boolean isEmpty() {
		return size() == 0;
	}
}
